package org.hot100_1;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class leetcode69 {
    public int[] topKFrequent(int[] nums, int k) {
        int [] res = new int[k];

        Map<Integer,Integer> map = new HashMap<>();

        //统计频率，map的key为num，value为对应的频率
        for (int num:nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }

        //构建小顶堆
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((pair1,pari2)->pair1[1]-pari2[1]);

        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (priorityQueue.size()<k){
                priorityQueue.add(new int[]{entry.getKey(),entry.getValue()});
            }else {
                //只有当前的遍历的频率大于堆顶的元素，并且堆已经满了，才对小顶堆进行更新操作
                //如果堆已经满了，但是频率比堆顶的元素还小，说明这个频率太小了，不在考虑的范围内
                if (entry.getValue()>priorityQueue.peek()[1]){
                    priorityQueue.poll();
                    priorityQueue.add(new int[]{entry.getKey(),entry.getValue()});
                }
            }
        }

        for (int i = 0; i < k; i++) {
            res[i]=priorityQueue.poll()[0];
        }

        return res;
    }
}
